package class09;

import class09.LinkedTools.*;
import java.util.ArrayList;

public class Code01_LinkedListMid {

    // 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
    public static ListNode midOrUpMidListNode(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
    public static ListNode midOrDownMidListNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
    public static ListNode midOrUpMidPreListNode(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head, fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
    public static ListNode midOrDownMidPreListNode(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head, fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static ListNode right1(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ArrayList<ListNode> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 1) / 2);
    }

    public static ListNode right2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ArrayList<ListNode> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get(arr.size() / 2);
    }

    public static ListNode right3(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode cur = head;
        ArrayList<ListNode> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 3) / 2);
    }

    public static ListNode right4(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode cur = head;
        ArrayList<ListNode> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 2) / 2);
    }

    public static void main(String[] args) {
        ListNode test;
        test = new ListNode(0);
        test.next = new ListNode(1);
        test.next.next = new ListNode(2);
        test.next.next.next = new ListNode(3);
        test.next.next.next.next = new ListNode(4);
        test.next.next.next.next.next = new ListNode(5);
        test.next.next.next.next.next.next = new ListNode(6);
        test.next.next.next.next.next.next.next = new ListNode(7);
        test.next.next.next.next.next.next.next.next = new ListNode(8);
        test.next.next.next.next.next.next.next.next.next = new ListNode(9);

        ListNode ans1, ans2;

        ans1 = midOrUpMidListNode(test);
        ans2 = right1(test);
        System.out.println(ans1 == ans2 ? "" : "错误");
        // System.out.println(ans1 != null ? ans1.value : "无");
        // System.out.println(ans2 != null ? ans2.value : "无");

        ans1 = midOrDownMidListNode(test);
        ans2 = right2(test);
        System.out.println(ans1 == ans2 ? "" : "错误");
        // System.out.println(ans1 != null ? ans1.value : "无");
        // System.out.println(ans2 != null ? ans2.value : "无");

        ans1 = midOrUpMidPreListNode(test);
        ans2 = right3(test);
        System.out.println(ans1 == ans2 ? "" : "错误");
        // System.out.println(ans1 != null ? ans1.value : "无");
        // System.out.println(ans2 != null ? ans2.value : "无");

        ans1 = midOrDownMidPreListNode(test);
        ans2 = right4(test);
        System.out.println(ans1 == ans2 ? "" : "错误");
        // System.out.println(ans1 != null ? ans1.value : "无");
        // System.out.println(ans2 != null ? ans2.value : "无");
    }

}
